      1  import java.util.ArrayList;

      2

      3  /**

      4     This program computes permutations of a string.

      5  */

      6  public class Permutations

      7  {

      8     public static void main(String[] args)

      9     {

     10        for (String s : permutations("eat"))

     11        {

     12           System.out.println(s);

     13        }

     14     }

     15

     16     /**

     17        Gets all permutations of a given word.

     18        @param word the string to permute

     19        @return a list of all permutations

     20     */

     21     public static ArrayList<String> permutations(String word)

     22     {

     23        ArrayList<String> result = new ArrayList<String>();

     24

     25        // The empty string has a single permutation: itself

     26        if (word.length() == 0)

     27        {

     28           result.add(word);

     29           return result;

     30        }

     31        else

     32        {

     33           // Loop through all character positions

     34           for (int i = 0; i < word.length(); i++)

     35           {

     36              // Form a shorter word by removing the ith character

     37              String shorter = word.substring(0, i) + word.substring(i + 1);

     38

     39              // Generate all permutations of the simpler word

     40              ArrayList<String> shorterPermutations = permutations(shorter);

     41

     42              // Add the removed character to the front of

     43              // each permutation of the simpler word,

     44              for (String s : shorterPermutations)

     45              {

     46                 result.add(word.charAt(i) + s);

     47              }

     48           }

     49           // Return all permutations

     50           return result;

     51        }

     52     }

     53  }

     54